import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yang
 * Date: 2022-07-16
 * Time: 18:52
 */
public class PriorityQueue {//创建一个小根堆
    private int[] elem;
    private int usedSize;
    PriorityQueue(){
        elem = new int[10];
        usedSize = 0;
    }

    PriorityQueue(int[] array){
        elem = Arrays.copyOf(array,array.length);
        usedSize = array.length;
        for(int parent = (usedSize-1-1)/2; parent >= 0; parent--){
            shiftDown(parent);
        }

    }

    private void swap(int a,int b,int[] array){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    private void shiftDown(int parent){
        int child = 2*parent + 1;
        while(child < usedSize){
            if(child+1 < usedSize && elem[child] > elem[child + 1]){
                child++;
            }
            if(elem[parent] > elem[child]){
                swap(parent,child,elem);
                parent = child;
                child = 2*parent + 1;
            }
            else break;
        }
    }

    private void shiftUp(int child){
        while(child > 0){
            int parent = (child - 1)/2;
            if(elem[child] < elem[parent]){
                swap(child,parent,elem);
                child = parent;
            }
            else break;
        }
    }

    public void offer(int num){
        if(usedSize == elem.length){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = num;
        shiftUp(usedSize);
        usedSize++;
    }

    public int peek(){
        return elem[0];
    }

    public int pull(){
        swap(0,usedSize-1,elem);
        shiftDown(0);
        usedSize--;
        return elem[usedSize];
    }

    public static void main(String[] args) {
        int[] arr = {3,4,2,5,6};
        PriorityQueue q = new PriorityQueue(arr);
        q.offer(12);
        q.offer(4);
        q.offer(5);
        System.out.println(q.pull());
        System.out.println(q.peek());
    }
}
